1. Field of the Invention
This invention relates to a binary tree arrangement storing fixed or variable length keys, and a method and apparatus for locating the insert arc or node in such an arrangement.
2. Introduction
The invention provides a novel binary tree arrangement for a machine representation storing both fixed and variable length keys, together with their lengths, organized by the nodes and connections between nodes in said binary tree. The arrangement minimizes the storage required for the machine representation of said nodes, connections, keys and their lengths.
The invention provides method and means for controlling the locating step(s) of a binary tree insertion operation, It uses a principle based on a minimal difference or a maximal similarity relationship among the keys stored in the tree.
The embodiments of this invention include unique methods and apparatus for controlling the execution of a computer. This application describes the steps performed and the machine representation in sufficient detail that a person skilled in the art can make and use them in hardware, microprogram, or program. Thus the inventions can be utilized in either a special purpose or general purpose computer system.
The invention provides the control logic for said insertion method in a binary tree having said novel binary tree arrangement, said control logic minimizing the number of storage accesses and stores for carrying out said locating step(s) and inserting operation, and minimizing the amount of elapsed time required for a machine to execute said operations.
The invention provides both method and means for said control logic that is especially suited for direct use in a special purpose apparatus for executing the subject processes, and especially suited for incorporation in a reduced instruction set computer (RISC) in the form of instructions which can be executed in a single cycle.
The methods and apparatus of the invention provide economic advantage for sorting and indexing, which are heavily used in commercial computing environments; especially providing a competitive economic advantage for computer execution of database operations and associative classes in object oriented programming, logic programming, and constraint logic programming.
3. Description of the Prior Art
The prior art includes publications such as "Sorting and Searching", by D. E. Knuth, published in 1973 by Addison Wesley. The prior art also includes the following U.S. patents: U.S. Pat. No. 3,916,387 "Direcory Searching Method and Means", and U.S. Pat. No. 4,086,628 "Directory Generation System Having Efficiency Increase with Sorted Input."
The above prior art apply to searching and inserting in binary trees, where a forward path trace is followed by a backward path trace to complete an insert. The path trace utilizing the forward and backward path trace to locate the insert arc enables the prior art to locate the insert arc by processing a number of nodes approximately equal to 1.4 times the base two logarithm of the number of keys in the tree, plus the nodes on the backward path trace.
The prior art includes "Blasting Through The Information Theoretic Barrier With FUSION TREES", by Michael L. Frednam and Dan E. Willard, published in the Proceedings of the 22-nd ACM Symposium on Theory for Computing, (1990), pp. 1-7. In this prior art, multiplication is used to select bits of a key in order to form an index into a complete binary tree having a number for entries that is an exact power of two.
This prior art utilizes an insertion method requiring polynomial time for new nodes in a multiway tree. As a result, claims for faster sorting in this prior art apply only to ernormously large numbers of entries, as the "constant" time to use for each sub-logarithmic operation is so huge that it would require having trillions of entries before the time is competitive with other art.
More closely related prior art is "New Trie Data Structures Support Very Fast Search Operations", by Dan E. Willard, published in the Journal of Computing and System Sciences, volume 28, in 1984, pp. 379-394. In this prior art, two keys are stored at each binary tree node. Searching and inserting follow a downward path trace, starting from a top node. Said two keys are selected from the left and right subtrees, respectively, of said binary tree node. Said downward path trace proceeds by forming two quantities by exclusive-oring a new key with said two stored keys, and then comparing the two quantities. The lower of the two quantities determines whether the new key directs the downward path trace into said left or said right subtree of said node.
Also stored at each binary tree node are pointers to the subtrees of said node. Thus the space requirements are at least four words per entry, and in practice are more, because of the encoding of terminal nodes. No means nor method for backtrace is provided.
The above prior art mentions forming a multilevel tree structure by utilizing trees for each level, wherein the keys are restricted to the word length of the machine. The first level is thus represented by a first level tree. At the end of each path in the first level tree is a pointer to a next level tree for the next word in the key, and so on. No encoding methods, no arrangements of the fields to accomplish the multilevel encoding, are disclosed.
The above prior art does not provide for variable length keys, except for U.S. Pat. No. 3,916,387 which does not elaborate the actual representation for variable length key support.
In the prior art U.S. Pat. No. 3,916,387 no part of any key is stored in the tree, but all locating is done by means of bit testing. It is somewhat similar to the Fusion Tree methods, except that the Fusion Tree methods espouse the use of multiplcation for decoding multiple bits for path tracing.